Technical Field
The present invention relates to a system and method for accelerating and/or optimizing performance for applications, and more particularly, to a source-to-source compiler and run-time library to transparently accelerate and/or optimize performance on stack or queue-based irregular applications on many-core architectures.
Description of the Related Art
Many-core graphics processor units (GPUs) have shown promising results for the applications that can utilize massive thread level parallelism (TLP) in last few years. For example, either a single Intel Many Integrated Core or a single General-purpose computing on graphics processing units (GPGPU) can provide Teraflops computation power in a second. However it currently remains a challenge to achieve high performance for irregular applications that operate on special data structures. For example, in order to minimize the computational complexity, the implementation of breadth first search (BFS) needs to maintain a queue as the frontier. The queue structure is widely used by many graph algorithms. Another example is the stack, which can be used to trace back in graphic algorithms, (e.g., Raytracing).
While queue structures and stack structures are very fundamental and widely used by application developers, there are several major limitations for using these data structures on GPGPUs. For example, due the lack of the mature implementations like C++ STL, application developers have to implement them by themselves on GPGPUs, and this requires additional effort and complicates the source code. Moreover, depending on the application developers background regarding computer hardware, the implementations of these data structures can have significant impact on the performance. It is noted that on CPUs, there may existing libraries which can be used by developers when using queues or stacks. However, on General-purpose computing on graphics processors (GPGPUs), such libraries are not available, and developers can only implement them using raw array access.